package 其他.猿辅导;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 全排列回溯3_复习子集全排和k {
    static int[] p;
    static boolean[] vis;
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> tmp = new ArrayList<>();

    static int n,m,k,x;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] s1 = s.split(" ");
        n = Integer.parseInt(s1[0]);
        k = Integer.parseInt(s1[1]);
        m = Integer.parseInt(s1[2]);
        x = Integer.parseInt(s1[3]);

        String s2 = scanner.nextLine();
        String[] s3 = s2.split(" ");
        p = new int[s3.length];
        for (int i = 0; i < s3.length; i++) {
            p[i] = Integer.parseInt(s3[i]);
        }

        vis = new boolean[s3.length];
        for (int i = 0; i < s3.length; i++) {
            vis[i] = false;
        }
        //1
        bT(0,k);
        System.out.println(res);

        for (int i = 0; i < p.length; i++) {
            List<Integer> tmp = new ArrayList<>();
            for (int j = 0; j < k; j++) {
                tmp.add(p[i]);
            }
            res.add(tmp);
        }

        // 2
        int resCount = 0;
        for (int i = 0; i < res.size(); i++) {
            if(getZJnum(res.get(i)) && isXk(res.get(i)) ){
                resCount++;
            }
        }
    }
    private static boolean isXk(List<Integer> tmp) {
        int sum = 0;
        for (int i = 0; i < tmp.size(); i++) {
            int c = tmp.get(i);
            sum = sum*10 + c;
        }
        if(sum %x == m){
            return true;
        }
        return false;
    }
    static boolean getZJnum(List<Integer> tmp){
        for (int i = 0; i < tmp.size()-1; i++) {
            int cS = tmp.get(i) + tmp.get(i+1);
            if(cS%2==0){
                return false;
            }
        }
        return true;
    }
    static void bT(int cI, int k){
        if(tmp.size() == k){
            res.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = 0; i < p.length ; i++) {
            if(!vis[i]) {
                tmp.add(p[i]);
                vis[i] = true;
                bT(i, k);
                vis[i] = false;
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}
